import java.util.*;

/**
 * Created whit IntelliJ IDEA.
 * Description：
 * User：ZHONGCHEN
 * Date:2022-02-04
 * Time:21:28
 */
public class TestDemo {
    /**
     * 可以形成最大正方形的矩形数目
     * 输入：rectangles = [[5,8],[3,9],[5,12],[16,5]]
     * 输出：3
     * 解释：能从每个矩形中切出的最大正方形边长分别是 [5,3,5,5] 。
     * 最大正方形的边长为 5 ，可以由 3 个矩形切分得到
     */
    public static int countGoodRectangles1(int[][] rectangles) {
        int num = 0;
        ArrayList<Integer> list = new ArrayList<>();
        //把二维数组中每一个一维数组中的最小值取出来
        for (int[] ret : rectangles) {
            if (ret[0] < ret[1]) {
                list.add(ret[0]);
            } else {
                list.add(ret[1]);
            }
        }
        int max = 0;
        for (Integer a : list) {
            if (a >= max) {
                //若a>max 则说明 max需要发生改变 num需要重新开始计算
                if (a > max) {
                    num = 0;
                }
                num++;
                max = a;
            }
        }
        return num;
    }

    /**
     * 在遍历过程中使用变量 max 维护最大边长，同时使用 ans 记录能够分割出最大边长 max 的矩形数量。
     */
    public static int countGoodRectangles(int[][] rectangles) {
        int max = 0;
        int ans = 0;
        for (int[] r : rectangles) {
            int cur = Math.min(r[0], r[1]);
            if (cur == max) {
                ans++;
            } else if (cur > max) {
                max = cur;
                ans = 1;
            }
        }
        return ans;
    }

    public static void main1(String[] args) {
        int[][] rectangles = {{2, 3}, {3, 7}, {4, 3}, {3, 7}};
        System.out.println(countGoodRectangles(rectangles));
    }

    /**
     * 和为 K 的最少斐波那契数字数目 1414
     * 给你数字 k ，请你返回和为 k 的斐波那契数字的最少数目，其中，每个斐波那契数字都可以被使用多次。
     * 输入：k = 7
     * 输出：2
     * 解释：斐波那契数字为：1，1，2，3，5，8，13，……
     * 对于 k = 7 ，我们可以得到 2 + 5 = 7 。
     * <p>
     * 思路：首先找到所有不超过 k的斐波那契数字，
     * 然后每次贪心地选取不超过 k的最大斐波那契数字，
     * 将 k减去该斐波那契数字，重复该操作直到 k变为 0，
     * 此时选取的斐波那契数字满足和为 k且数目最少。
     * <p>
     * 结论1：当选取斐波那契数字数目最少时，不可能选取两个相邻的斐波那契数
     * 结论2：一定存在一种选取斐波那契数字数目最少的方案，使得选取的每个斐波那契数字各不相同
     * 结论3：根据上述两个结论，必须选取不超过 k的最大斐波那契数字，
     * 才能使得选取的斐波那契数字满足和为 k且数目最少
     */
    public static int findMinFibonacciNumbers(int k) {
        int a = 1;
        int b = 1;
        //找出离k最近的斐波那契数
        while (b <= k) {
            int c = a + b;
            System.out.print(c + " ");
            a = b;
            b = c;
        }
        System.out.println();
        System.out.println(" ============= ");
        //记录答案的个数
        int ans = 0;
        while (k != 0) {

            if (k >= b) {
                k -= b;
                ans++;
                System.out.print(b + " ");
            }
            //利用斐波那契数列的递推性质
            int c = b - a;
            b = a;
            a = c;
        }
        return ans;
    }

    public static void main3(String[] args) {
        System.out.println(findMinFibonacciNumbers(232));
    }

    //唯一元素的和
    //给你一个整数数组 nums 。数组中唯一元素是那些只出现 恰好一次 的元素。
    //请你返回 nums 中唯一元素的 和 。
    public static int sumOfUnique(int[] nums) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int a : nums) {
            if (map.containsKey(a)){
                map.put(a,map.get(a)+1);
            }else {
                map.put(a,1);
            }
        }
        int sum = 0;
        for (int a :nums) {
            if (map.get(a) == 1){
                sum+=a;
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] arr = {1,2,3,2};
        System.out.println(sumOfUnique(arr));
    }
}
